/**
 * 排列序列
 *
 * 给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * 给定 n 和 k，返回第 k 个排列。
 *
 * 示例 1：
 * 输入：n = 3, k = 3
 * 输出："213"
 *
 * 示例 2：
 * 输入：n = 4, k = 9
 * 输出："2314"
 *
 * 示例 3：
 * 输入：n = 3, k = 1
 * 输出："123"
 *
 * 提示：
 * 1 <= n <= 9
 * 1 <= k <= n!
 */

/**
 * 1. 回溯, 有顺序的全排列, 不过这题我们取到第 k 个就可以
 * 返回结果了
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n)
 *
 * 2. 用数学方法, 我们可以知道一个全排列, 每个数字开头的排列都有
 * (n - 1)! 的种树, 所以我们可以利用这点, 在已知 k 的情况下, 得
 * 到所要求的排列所在的一个范围
 */

public class Main {

    // 定义全局变量
    int n;
    int k;
    boolean[] isValid;
    StringBuffer s;

    // 用来记录求到的第几种
    int tmp;

    public String getPermutation(int nn, int kk) {

        // 初始化
        n = nn;
        k = kk;
        isValid = new boolean[n + 1];
        s = new StringBuffer();
        tmp = 0;

        dfs(0);
        return s.toString();
    }

    private void dfs (int m) {

        // 要是到达情况返回
        if (m == n) {

            // 达到情况了种数要加一
            tmp++;
            return;
        }

        for (int i = 1; i <= n; i++) {

            // 深搜
            if (!isValid[i]) {
                s.append(i);
                isValid[i] = true;

                dfs(m + 1);

                // 要是到达已求种数, 返回
                if (tmp == k) {
                    return;
                }

                // 恢复现场
                isValid[i] = false;
                s.deleteCharAt(s.length() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Main test = new Main();
        System.out.println(test.getPermutation(3, 3));
    }
}